/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package binarysearchtree;

public class BSTree<T1 extends Comparable<T1>, T2> {

    static class Node<T1, T2> {

        T1 key;
        T2 value;
        Node<T1, T2> left, right;

        Node(T1 key, T2 value) {
            this.key = key;
            this.value = value;
        }

        public String toString() {
            return "[" + key + "," + value + "]";
        }
    }
    
    /** The tree root. */
    private Node<T1, T2> root = null;
    
    /**
     * Print tree in in order walk
     * @param x the node that roots the tree
     * @param s indentation from root of the tree
     */
    public void printInorderTree(Node<T1, T2> x, String s) {
        if (x.right != null) {
            printInorderTree(x.right, s + "\t");
        }
        System.out.println(s + x.toString());
        if (x.left != null) {
            printInorderTree(x.left, s + "\t");
        }
    }

    /**
     * Print tree in post order walk
     * @param x the node that roots the tree
     */
    public void printPostOrder(Node<T1, T2> x) {
        if (x.left != null) {
            printPostOrder(x.left);
        }
        if (x.right != null) {
            printPostOrder(x.right);
        }
        System.out.println(x.toString());
    }

    /**
     * Print tree in pre order walk
     * @param x the node that roots the tree
     */
    public void printPreOrder(Node<T1, T2> x) {
        System.out.println(x.toString());
        if(x.left != null)
            printPreOrder(x.left);
        if(x.right != null)
            printPreOrder(x.right);
    }
    
    /** 
     * Method to get root of tree.
     * @return the root of the tree.
     */
    public Node getRoot() {
        return root;
    }
    
    /**
     * Internal method to find item in subtree.
     * @param x the node that roots the tree.
     * @param k the key of item to find.
     * @return the matching item or null if not found.
     * @throws ItemNotFoundException if x is not exist.
     */
    private Node<T1, T2> find(Node<T1, T2> x, T1 k) {
        if(x == null)
            throw new ItemNotFoundException();
        if(k.compareTo(x.key) == 0)
            return x;
        else if(k.compareTo(x.key) < 0)
            return find(x.left, k);
        else
            return find(x.right, k);     
    }
    
    /**
     * 
     * @param k the key of item to find.
     * @return the matching item or null if not found.
     * @throws ItemNotFoundException if x is not exist.
     */    
    public Node<T1, T2> find(T1 k) {
         return find(root, k);
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the node that roots the tree.
     * @param k the key of item to insert.
     * @param v the value if item to insert.
     * @return DuplicateItemException if node is already present.
     */
    private Node<T1, T2> insert(Node<T1, T2> x, T1 k, T2 v) {
        if(x == null){
            x = new Node<T1, T2>(k, v);
        } else {
            int cmp = k.compareTo(x.key);
            if(cmp < 0) {
                x.left = insert(x.left, k, v);
            } else if(cmp > 0){
                x.right = insert(x.right, k, v);
            } else
                throw new DuplicateItemException(k.toString());
        }
        return x;
    }
    
    /**
     * Insert into the tree 
     * @param k the key of item to insert.
     * @param v the value if item to insert.
     * @throws DuplicateItemException if node is already present.
     */
    public void insert(T1 k, T2 v) {
        root = insert(root, k, v);
    }
    
    /**
     * Internal method to remove from a subtree.
     * @param node the node that roots the tree.
     * @param k the key of item to remove.
     * @return the new root.
     * @throws ItemNotFoundException if node is not found.
     */
    private Node<T1, T2> remove(Node<T1, T2> x, T1 k){
        if(x == null)
            throw new ItemNotFoundException();
        if(k.compareTo(x.key) < 0)
            x.left = remove(x.left, k);
        else if(k.compareTo(x.key) > 0)
            x.right = remove(x.right, k);
        else if(x.left != null && x.right != null){
            x.key = findMin(x.right).key;
            x.right = removeMin(x.right);
        }
        return x;
    }
    
    /**
     * Remove from the tree.
     * @param k key of the item to remove.
     * @throws ItemNotFoundException if node is not found.
     */
    public void remove(T1 k){
        root = remove(root, k);
    }
    
    /**
     * Internal method to remove minimum item from a subtree
     * @param x the node that roots the tree.
     * @return the new root.
     * @throws ItemNotFoundException if x is not found.
     */
    private Node<T1, T2> removeMin(Node<T1, T2> x){
        if(x == null)
            throw new ItemNotFoundException();
        else if (x.left != null){
            x.left = removeMin(x.left);
            return x;
        } else 
            return x.right;
    }
    
    /**
     * Internal method to find the smallest item in a subtree.
     * @param x the node that the roots the tree.
     * @return node containing the smallest item.
     */
    private Node<T1, T2> findMin(Node<T1, T2> x){
        if(x != null)
            while(x.left != null)
                x = x.left;
        return x;
    }    
}